Brought to you by EarthWeb
IT Library Logo

Click Here!
Click Here!


Search the site:
 
EXPERT SEARCH -----
Programming Languages
Databases
Security
Web Services
Network Services
Middleware
Components
Operating Systems
User Interfaces
Groupware & Collaboration
Content Management
Productivity Applications
Hardware
Fun & Games

EarthWeb Direct EarthWeb Direct Fatbrain Auctions Support Source Answers

EarthWeb sites
Crossnodes
Datamation
Developer.com
DICE
EarthWeb.com
EarthWeb Direct
ERP Hub
Gamelan
GoCertify.com
HTMLGoodies
Intranet Journal
IT Knowledge
IT Library
JavaGoodies
JARS
JavaScripts.com
open source IT
RoadCoders
Y2K Info

Previous Table of Contents Next


CONVENTIONAL ENCRYPTION

PGP exploits two powerful security functions: conventional encryption and public-key encryption. Conventional encryption is the classic approach to secret codes that dates back to the time of ancient Rome and even earlier. A conventional encryption scheme (see Exhibit 8-7-1) includes the following five ingredients:

  Plaintext. This is the readable message or data that is fed into the algorithm as input.
  Encryption algorithm. The encryption algorithm performs various substitutions and transformations on the plaintext.
  Secret key. The secret key is also input to the algorithm. The exact substitutions and transformations performed by the algorithm depend on the key.
  Ciphertext. This is the scrambled message produced as output. It depends on the plaintext and the secret key.
  Decryption algorithm. This is essentially the encryption algorithm run in reverse. It takes the ciphertext and the same secret key and produces the original plaintext.


Exhibit 8-7-1.  Conventional Encryption

The Caesar cipher, used by Julius Caesar, is a simple example of encryption. The Caesar cipher replaces each letter of the alphabet with the letter standing three places further down the alphabet, for example:

                     plain: meet me after the toga party
                    cipher: phhw ph diwhu wkh wrjd sduwb

The alphabet is wrapped around so that the letter following Z is A. The decryption algorithm simply takes the ciphertext and replaces each letter with the letter standing three places earlier on in the alphabet. A general Caesar cipher involves a shift of k letters, where k ranges from 1 through 25. In this case, k is the secret key to the algorithm.

The Caesar cipher is not very secure. Anyone who wanted to decipher the code could simply try every possible shift from 1 to 25. PGP uses a much stronger algorithm known as the International Data Encryption Algorithm, or IDEA.

The International Data Encryption Algorithm

IDEA is a block-oriented conventional encryption algorithm developed in 1990 by Xuejia Lai and James Massey of the Swiss Federal Institute of Technology. The overall scheme for IDEA encryption is illustrated in Exhibit 8-7-2. IDEA uses a 128-bit key to encrypt data in blocks of 64 bits.


Exhibit 8-7-2.  Overall IDEA Structure

The IDEA algorithm consists of eight rounds, or iterations, followed by a final transformation function. The algorithm breaks the input into four 16-bit subblocks. Each of the iteration rounds takes four 16-bit subblocks as input and produces four 16-bit output blocks. The final transformation also produces four 16-bit blocks, which are concatenated to form the 64-bit ciphertext. Each of the iterations also uses six 16-bit subkeys, whereas the final transformation uses four subkeys, for a total of 52 subkeys. The right-hand portion of the exhibit indicates that these 52 subkeys are all generated from the original 128-bit key.

Each iteration of IDEA uses three different mathematical operations. Each operation is performed on two 16-bit inputs to produce a single 16-bit output. The operations are:

  Bit-by-bit exclusive-OR, denoted as (+).
  Addition of integers modulo 216 (modulo 65536), with input and output treated as unsigned 16-bit integers. This operation is denoted as [theta].
  Multiplication of integers modulo 216 + 1 (modulo 65537), with input and output treated as unsigned 16-bit integers, except that a block of all zeros is treated as representing 216. This operation is denoted as [theta].

For example,

    0000000000000000 [theta] 1000000000000000 = 1000000000000001

because

216 × 215 mod (216 + 1) = 215 + 1

These three operations are incompatible because no pair of the three operations satisfies a distributive law. For example:

a (b[theta] c)[not equal to](a b) [theta] (a c)

They are also incompatible because no pair of the three operations satisfies an associative law. For example,

a (b(+)c)[not equal to](a b)(+)c

the use of these three separate operations in combination provides for a complex transformation of the input, making cryptanalysis very difficult.

Exhibit 8-7-3 illustrates the algorithm for a single iteration. In fact, this exhibit shows the first iteration. Subsequent iterations have the same structure, but with different subkey and plaintext-derived input. The iteration begins with a transformation that combines the four input subblocks with four subkeys, using the addition and multiplication operations. This transformation is highlighted as the upper shaded rectangle. The four output blocks of this transformation are then combined using the XOR operation to form two 16-bit blocks that are input to the lower shaded rectangle, which also takes two subkeys as input and combines these inputs to produce two 16-bit outputs.


Exhibit 8-7-3.  Single Iteration of IDEA (First Iteration)

Finally, the four output blocks from the upper transformation are combined with the two output blocks of the MA structure using XOR to produce the four output blocks for this iteration. The two outputs that are partially generated by the second and third inputs (X2 and X3) are interchanged to produce the second and third outputs (W12 and W13), thus increasing the mixing of the bits being processed and making the algorithm more resistant to cryptanalysis.

The ninth stage of the algorithm, labeled the output transformation stage in Exhibit 8-7-2, has the same structure as the upper shaded portion of the preceding iterations (see Exhibit 8-7-3). The only difference is that the second and third inputs are interchanged before being applied to the operational units. This has the effect of undoing the interchange at the end of the eighth iteration. This extra interchange is done so that decryption has the same structure as encryption. This ninth stage requires only four subkey inputs, compared to six subkey inputs for each of the first eight stages. The subkeys for each iteration are generated by a series of shifts on the original 128-bit key.

IDEA has advantages over older convetional encryption techniques. The key length of 128 bits makes it resistant to brute-force key search attacks. IDEA is also very resistant to cryptanalysis and was designed to facilitate both software and hardware implementations.


Previous Table of Contents Next

footer nav
Use of this site is subject certain Terms & Conditions.
Copyright (c) 1996-1999 EarthWeb, Inc.. All rights reserved. Reproduction in whole or in part in any form or medium without express written permission of EarthWeb is prohibited. Please read our privacy policy for details.